State of the art navigation devices provide a large amount of useful information and search options regarding routes to be travelled, Point Of Interests (POIs) in the vicinity of calculated routes or in the vicinity of a device position, names of cities, streets or buildings, traffic information and so on. Depending on the services the navigation device is going to provide, navigation devices store large amounts of navigation data associated with, for example, routing, map displaying, destination entry, POIs, traffic information in their databases.
One problem related with state of the art navigation devices consists in efficiently updating large navigation databases. In practice, routing data, destination entry data, map display data, POI data, etc. have to be regularly updated in order to take into account continuous changes in the road network, POI network, and so on. However, since stored navigation data are highly interlinked (especially destination entry data, routing data and map display data) and since the database design has to take into account limited computational power of mobile or embedded navigation devices, a database update generally ends up with replacing the whole dataset or large data blocks of the dataset.
In current solutions large updatable data blocks comprise navigation data associated with large geographical areas, such as (federal) states (e.g., California), countries, group of countries (e.g., BENELUX: Belgium, Netherlands and Luxemburg), or individual continents (e.g., Australia, Europe). A partial or incremental update, in which a sub-set of an updatable data block is replaced (for instance, a data sub-set representing a local geographic area of 40 km×40 km (called local tile hereinafter) is—for consistency reasons of the whole database—hardly possible. The reason for this is the fact that navigation data elements within the database are highly interlinked so that replacement of individual data elements within one or more data sub-sets associated with local geographic areas may entail navigation data modifications of the whole updatable data block or database.
Further, navigation data and navigation systems are often provided by different suppliers. Thus, state of the art navigation systems generally use proprietary navigation data formats. Consequently, navigation data suppliers have to provide navigation data and update packages for all data formats being on the market, causing high efforts and costs on the side of the navigation data suppliers.
A further problem associated with state of the art navigation devices and navigation databases is that, even in case a navigation device supports limited data updates in form of patch updates, the patch history might depend on the navigation device supplier and, therefore, it might vary for each navigation device. In order to provide each individual system with appropriate patches, a patch history has to be recorded and provided to a corresponding navigation data server. Complex patch histories, however, comprise an increasing amount of data and require additional hardware resources, such as additional storage resources on the navigation system, transmission resources, and so on. Further, with individual patches, the variance of navigation databases increases, and testing for qualification of patches as well as diagnosis of errors occurring on individual systems becomes increasingly complex and expensive.
In order to simplify the provisioning and updating of navigation data, a navigation system independent physical storage format has been developed by Navigation Data Standard (NDS) e.V., a registered German society of car manufactures, navigation system suppliers and map suppliers. The NDS format allows a more flexible updating of NDS databases and supports data retrieval from different data suppliers and via different distribution channels without losing database consistency. However, incremental navigation data update on local (e.g., tile) basis is presently not supported by NDS.